% This project is a template slides for the subsequent presentations which are significant during the postgraduate period.
% Template for College of Information Science and Electronic Engineering, Zhejiang University.
% Compiled with pdflatex.
% By Xue Shengke.
% The bib for this template is bibtex not biber

\documentclass[10pt, mathserif]{beamer}	% font and size
\mode<presentation>
{
    \setbeamercovered{dynamic}	% translucent when using pause
    \setbeamertemplate{navigation symbols}{}	% hide navigation bars
    \setbeamertemplate{caption}[numbered]	% numerate captions
    % \setbeamertemplate{background}{\includegraphics[height=\paperheight]{ISEE.pdf}}	% set background image
    \setbeamertemplate{footline}{\textcolor{light-gray}{\scriptsize \insertframenumber/\inserttotalframenumber} \hfill}	% display page number at bottom left corner	
}
\usepackage{ctex}
% \usepackage{xeCJK}
\usepackage{times}		% font for english, Times New Roman
\usepackage{amsmath, amsfonts, amssymb}	% math equations, symbols
\usepackage[english]{babel}
\usepackage{color}		% color content
\usepackage{graphicx}	% import figures
\usepackage{subfigure}
\usepackage{url}		% hyperlinks
\usepackage{bm}			% bold type for equations
\usepackage{hyperref}
\hypersetup{hypertex=true,
            colorlinks=true,
            linkcolor=blue,
            anchorcolor=blue,
            citecolor=blue}
\usepackage{multirow}
\usepackage{listings}
\usepackage{xcolor}
% \setCJKsansfont{黑体}	% all Chinese should be enclosed between the commands

% set font
\setCJKfamilyfont{yh}{Microsoft YaHei}

% set line space
\linespread{1.5}

\newcommand{\ftitle}[1]{\frametitle{#1}}	% userdefine frametitle
\definecolor{light-gray}{gray}{0.90}

\graphicspath{{figure/}}	% set graph path

% special for time line
\usepackage[utf8]{inputenc}
\usepackage[TS1,T1]{fontenc}
\usepackage{array, booktabs}
% \usepackage[x11names]{xcolor}
\usepackage{colortbl}
\usepackage{caption}
\definecolor{baseD}{HTML}{7CAFC2}
%baseD是一个很柔和的蓝色，你可以在相关github主页找到base16色的图样。
\newcommand{\foo}{\color{baseD}\makebox[0pt]{\textbullet}\hskip-0.5pt\vrule width 1pt\hspace{\labelsep}}

% 设置超链接
\hypersetup{hidelinks}
\def\equationautorefname        {式}
\def\footnoteautorefname        {脚注}
\def\figureautorefname          {Figure}
\def\tableautorefname           {表}
\def\partautorefname            {篇}
\def\chapterautorefname         {章}
\def\sectionautorefname         {节}
\def\subsectionautorefname      {小节}
\def\subsubsectionautorefname   {小小节}
\def\paragraphautorefname       {段落}
\def\subparagraphautorefname    {子段落}
\def\appendixautorefname        {附录}
\def\FancyVerbLineautorefname   {行}
\def\theoremautorefname         {定理}
\def\listoffigures              {代码}
\def\lstlistingname             {代码}

% 代码格式和颜色定义
% \definecolor{dkgreen}{rgb}{0,0.6,0}
% \definecolor{gray}{rgb}{0.5,0.5,0.5}
% \definecolor{comment}{rgb}{0.56,0.64,0.68}
% \lstset{
%   frame=tb,
%   aboveskip=3mm,
%   belowskip=3mm,
%   xleftmargin=2em,
%   xrightmargin=2em,
%   showstringspaces=false,
%   columns=flexible,
%   framerule=1pt,
%   rulecolor=\color{gray!35},
%   backgroundcolor=\color{gray!5},
%   basicstyle={\small\ttfamily},
%   numbers=left,
%   numberstyle=\tiny\color{gray},
%   keywordstyle=\color{blue},
%   commentstyle=\color{comment},
%   stringstyle=\color{dkgreen},
%   breaklines=false,
%   breakatwhitespace=true,
%   tabsize=2,
% }

\usepackage{fancybox}
\usepackage{xcolor}
\usepackage{times}
\usepackage{listings}

\usepackage{booktabs}
\usepackage{colortbl}

\newcommand{\Console}{Console}
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\definecolor{mygray}{gray}{.9}
\definecolor{mypink}{rgb}{.99,.91,.95}
\definecolor{mycyan}{cmyk}{.3,0,0,0}
\lstset{ %
    backgroundcolor=\color{white},   % choose the background color
    basicstyle=\footnotesize\rmfamily,     % size of fonts used for the code
    columns=fullflexible,
    breaklines=true,                 % automatic line breaking only at whitespace
    captionpos=b,                    % sets the caption-position to bottom
    tabsize=4,
    commentstyle=\color{mygreen},    % comment style
    escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
    keywordstyle=\color{blue},       % keyword style
    stringstyle=\color{mymauve}\ttfamily,     % string literal style
    numbers=left, 
    %	frame=single,
    rulesepcolor=\color{red!20!green!20!blue!20},
    % identifierstyle=\color{red},
    language=c
}
\usetheme{Frankfurt}

\def\R{\mathbb{R}}
\def\E{\mathbb{E}}
\def\st{\text{s.t.\ }}
\def\dom{\text{dom}}
\def\1{\textbf{1}}
\def\argmin{\text{argmin}}
\def\argmax{\text{argmax}}

\newtheorem{thm}{Theorem}


\captionsetup[figure]{labelformat={default},labelsep=period,name={图.}}

\title[abbreviation]{信息论(讨论)\footnote{CE Shannon\cite{shannon2001mathematical}, TM Cover\cite{cover1999elements}}}
\author{何扬槊 3180102687}
\institute[ISEE]{\normalsize 
        \includegraphics[width=0.2\textwidth]{ZJU_BLUE.pdf}  \\  % add a special logo on cover page
    信息与电子工程学院 \\
    浙江大学
    }
    \date{\today}
    
\begin{document}
\begin{frame}
    \titlepage	% make the cover page here
\end{frame}
    

\AtBeginSection[]
{
\begin{frame}
       \ftitle{Outline}		% contents for better review
    \tableofcontents[currentsection, currentsubsection]
\end{frame}
}


\section{通信系统}
\begin{frame}
    \frametitle{通信系统}

    \begin{figure}[H]
        \vspace{-0.5cm}
        \centering
        \includegraphics[width=7cm]{communication_system}
        \caption{通用的通信系统模型}
        \label{fig:communication_system}
    \end{figure}
    \vspace{-0.5cm}
    \begin{itemize}
        \item 信源: 产生消息序列
        \item 发送器: 对消息进行处理得到信号
        \item 信道: 信号传输的媒介，一般有噪声
        \item 接收器: 从信号重构消息
        \item 信宿: 消息接收者
    \end{itemize}
    

\end{frame}


\begin{frame}
    \frametitle{Basic Questions}

    \begin{enumerate}
        \item 如何衡量信息？
        \item 如何定义信源？
        \item 如何定义信道？
        \item 如何描述传输过程？
        \item 如何应对噪声？

    \end{enumerate}
    

\end{frame}


\section{信源}

\begin{frame}
    \frametitle{信源}

    \begin{itemize}
        \item 如何用数学语言描述信源？
        \item 离散信源产生多少信息？
    \end{itemize}
    

\end{frame}


\begin{frame}
    \frametitle{信源}

    \begin{itemize}
        \item 输出英文字母序列 A B A C A D C C
    \end{itemize}
    

\end{frame}

\begin{frame}
    \frametitle{信源}

    \begin{itemize}
        \item 输出英文字母序列 A B A C A D C C
        \item 离散信源逐个字符生成消息$\Longrightarrow$ 平稳随机过程
        % \item 度量信源生成消息的量
        \item Markov过程$X\rightarrow Z\rightarrow Y$
        \item 稳态分布
    \end{itemize}
    

\end{frame}

\subsection{马尔科夫过程}

\begin{frame}
    \frametitle{Markov过程}

    \begin{equation*}
        X\rightarrow Z\rightarrow Y
    \end{equation*}
    $Y$只与$Z$有关，与$X$无关
    \begin{equation}
        P(Y,X|Z) = P(Y|Z)P(X|Z)
    \end{equation}
    \begin{equation}
        P(Y|X,Z) = P(Y|Z)
    \end{equation}
    

\end{frame}

\begin{frame}
    \frametitle{Markov过程}
    不可约正常返的Markov链存在稳态分布($\boldsymbol{\pi} = [p_i],\ \boldsymbol{P} = \{P_{ij}\}$)
    \begin{equation}
        \boldsymbol{\pi} = \boldsymbol{\pi P}
    \end{equation}
    \begin{figure}[H]
        \centering
        \includegraphics[width=4cm]{markov_chain}
        \caption{Markov信源}
        \label{fig:markov_chain}
    \end{figure}

\end{frame}

\subsection{信源的熵} % 熵速率

\begin{frame}
    \frametitle{熵}
    \begin{itemize}
        \item 如何度量信源产生消息的量？
    \end{itemize}
    

\end{frame}

\begin{frame}
    \frametitle{熵}
    希望有一个度量$H(p_1,\cdots,p_n)$满足3个性质
    \begin{enumerate}
        \item $H$是$p$的连续函数
        \item $p_i = \frac{1}{n}$时，若$n\nearrow,\ H\nearrow$
        \item 一个选择被分为多个子选择，则原$H$为各个$H$的加权和
    \end{enumerate}
    \begin{figure}[H]
        
        \centering
        \includegraphics[width=4cm]{entropy_additive}
        \caption{熵的可加性要求}
        \label{fig:entropy_additive}
    \end{figure}
    \begin{equation*}
        H(\frac{1}{2},\frac{1}{3},\frac{1}{6}) = H(\frac{1}{2},\frac{1}{2}) + \frac{1}{2}H(\frac{1}{3},\frac{2}{3})
    \end{equation*}
    

\end{frame}

\begin{frame}[label=Appendix_entropy_back]
    \frametitle{熵}
    满足3个性质的函数有如下形式
    \begin{equation}
        H = -K\sum\limits_{i=1}^n p_i\log p_i
    \end{equation}
    $K$根据单位选取，bit一般取$K=1$

    \hyperlink{Appendix_entropy}{\beamergotobutton{Jump to Appendix}}

\end{frame}



\begin{frame}
    \frametitle{熵的性质}
    \begin{enumerate}
        \item $H(X) = 0\Longleftrightarrow p_i = 0 \text{ or } 1$
        \item $H(X)\leq \log n$
        \item $H(X)$ is concave in $p(x)$
    \end{enumerate}
    

\end{frame}

\begin{frame}
    \frametitle{熵的性质}
    \begin{itemize}
        
        \item 联合熵: $H(X,Y) = -\sum\limits_{x,y}p(x,y)\log p(x,y)$ \\
        $H(X) = -\sum\limits_{x,y}\log \sum\limits_y p(x,y)$
        \item $H(X,Y)\leq H(X) + H(Y)$
        \item 条件熵: $H(Y|X) = -\sum\limits_x p(y|x)\log p(y|x) = -\sum\limits_{x,y}p(x,y)\log p(y|x)$\\
        $H(Y|X) = H(X,Y) - H(X)$
        \item $H(Y)\geq H(Y|X)$
    \end{itemize}

\end{frame}

\begin{frame}
    \frametitle{熵的性质}
    \begin{itemize}
        
        \item 联合熵: $H(X,Y) = -\sum\limits_{x,y}p(x,y)\log p(x,y)$ \\
        $H(X) = -\sum\limits_{x,y}\log \sum\limits_y p(x,y)$
        \item $H(X,Y)\leq H(X) + H(Y)$
        \item 条件熵: $H(Y|X) = -\sum\limits_x p(y|x)\log p(y|x) = -\sum\limits_{x,y}p(x,y)\log p(y|x)$\\
        $H(Y|X) = H(X,Y) - H(X)$
        \item $H(Y)\geq H(Y|X)$
        \item $H(X,Y) = H(X) + H(Y|X)$ \\
        $H(X_1,\cdots,X_N) = \sum\limits_{n=1}^NH(X_n|X_1,\cdots,X_{n-1})$
    \end{itemize}

\end{frame}

\begin{frame}
    \frametitle{其他度量}
    \begin{itemize}
        \item 互信息: $I(X;Y) = \sum\limits_{x,y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$
    \end{itemize}

    

\end{frame}

\begin{frame}
    \frametitle{其他度量}
    \begin{itemize}
        \item 互信息: $I(X;Y) = \sum\limits_{x,y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$
        \begin{equation}
            \begin{split}
                I(X;Y) &= H(X) - H(X|Y) \\
                I(X;Y) &= H(Y)-H(Y|X) \\
                I(X;Y) &= H(X) + H(Y) - H(X,Y)
            \end{split}
        \end{equation}
    \end{itemize}
    \begin{figure}[H]
        \centering
        \includegraphics[width=6cm]{entropy_venn}
        \caption{熵的关系}
        \label{fig:entropy_venn}
    \end{figure}
    

\end{frame}

\begin{frame}
    \frametitle{其他度量}
    \begin{itemize}
        \item 互信息: $I(X;Y) = \sum\limits_{x,y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$
        \begin{equation*}
            \begin{split}
                I(X;Y) &= H(X) - H(X|Y) \\
                I(X;Y) &= H(Y)-H(Y|X) \\
                I(X;Y) &= H(X) + H(Y) - H(X,Y)
            \end{split}
        \end{equation*}
        \item $I(X;Y,Z) = I(X;Y) + I(X;Z|Y)$
    \end{itemize}
    

\end{frame}

\begin{frame}
    \frametitle{其他度量}
    \begin{itemize}
        \item KL散度: $D(p\|q) = \sum\limits_{x_1,\cdots,x_N} p(x_1,\cdots,x_N)\log \frac{p(x_1,\cdots,x_N)}{q(x_1,\cdots,x_N)}$
    \end{itemize}
    

\end{frame}

\begin{frame}
    \frametitle{其他度量}
    \begin{itemize}
        \item KL散度: $D(p\|q) = \sum\limits_{x_1,\cdots,x_N} p(x_1,\cdots,x_N)\log \frac{p(x_1,\cdots,x_N)}{q(x_1,\cdots,x_N)}$
        \item 描述两个分布的"\textcolor{red}{距离}"
        \begin{equation}
            D(p(x,y)\|p(x)p(y)) = I(X;Y)
        \end{equation}
    \end{itemize}
    

\end{frame}


\begin{frame}
    \frametitle{信源的熵}
    极限情况下可以由消息序列的统计量得到信源的熵

    $P(B_i)$为一个消息序列$B_i$的概率
    
    \begin{equation}
        G_N = -\frac{1}{N}\sum\limits_iP(B_i)\log P(B_i)
    \end{equation}
    消息序列$B_i$后面的符号为$s_j$
    \begin{equation}
        F_N = -\sum\limits_{i,j}P(B_i,s_j)\log P(s_j|B_i) - NG_N - (N-1)G_N
    \end{equation}
\end{frame}

\begin{frame}
    \frametitle{信源的熵}
    \begin{itemize}
        \item $N\nearrow,\ F_N\searrow$ (conditioning decrease entropy)
        \item $G_N = \frac{1}{N}\sum F_N \geq F_N$
        \item $\lim\limits_{N\rightarrow\infty} G_N = \lim\limits_{N\rightarrow\infty}F_N = H(\mathcal{S})$
    \end{itemize}
    \begin{definition}[熵速率]
        \begin{equation}
            H(\mathcal{S}) = \lim\limits_{N\rightarrow\infty}\frac{H(s^N)}{N}
        \end{equation}
    \end{definition}
\end{frame}


\begin{frame}[label=Appendix_AEP_back]
    \frametitle{信源的熵}
    考虑$N$长序列，为1阶Markov过程
    
    \begin{equation}
        H(\mathcal{S}) = -\sum\limits_{i,j}\pi_i p(j|i)\log p(j|i)
    \end{equation}

    进一步若符号$\{s_i\}$相互\textcolor{red}{独立}，信源的熵退化为符号的熵

    \begin{equation}
        H(\mathcal{S}) = H(S) = -\sum\limits_{i}P(s_i)\log P(s_i)
    \end{equation}
    

\end{frame}


\begin{frame}[label=Appendix_AEP_back]
    \frametitle{信源的熵}
    考虑$N$长序列，符号$\{s_i\}$相互独立，出现符号$s_i$的次数的\textcolor{red}{期望}为$p_iN$

    \begin{equation}
        \begin{split}
            \text{E}[P(s^N)] & = \text{E}[p] = \prod\limits_{i=1}^Np_i^{p_iN} \\
            \text{E}[-\frac{\log P(s^N)}{N}] & = -\frac{1}{N}\sum\limits_iNp_i\log p_i = H(\mathcal{S})
        \end{split}
    \end{equation}
    

\end{frame}

\begin{frame}[label=Appendix_AEP_back]
    \frametitle{信源的熵}
    考虑$N$长序列，符号$\{s_i\}$相互独立，出现符号$s_i$的次数的期望为$p_iN$

    \begin{equation*}
        \begin{split}
            \text{E}[P(s^N)] & = \text{E}[p] = \prod\limits_{i=1}^Np_i^{p_iN} \\
            \text{E}[-\frac{\log P(s^N)}{N}] & = -\frac{1}{N}\sum\limits_iNp_i\log p_i = H(\mathcal{S})
        \end{split}
    \end{equation*}
    \begin{definition}[典型列]
        \begin{equation}
            A_\epsilon^{(N)} = \{s^N:\mid -\frac{\log p}{N} - H(\mathcal{S})\mid\leq \epsilon\}
        \end{equation}
    \end{definition}
    \hyperlink{Appendix_AEP}{\beamergotobutton{Jump to Appendix}}

\end{frame}

\subsection{信源编码定理}

\begin{frame}
    \frametitle{信源编码定理}
    \begin{theorem}[离散无记忆信源编码定理]
        \label{thm:source_coding_thm}
        当编码速率$R$与信源的熵$H(\mathcal{S})$满足\autoref{equ:source_coding_thm}，错误概率$P_e^{(N)}\longrightarrow 0$
        \begin{equation}
            \label{equ:source_coding_thm}
            R < H(\mathcal{S})
        \end{equation}
        其中$R = \frac{\log M}{N},\ M$为码字的数量
    \end{theorem}
    

\end{frame}

\section{信道}

\begin{frame}
    \frametitle{信道}
    \begin{itemize}
        \item 如何用数学语言描述信号在信道传输的过程？
        \item 如何应对信号传输过程中引入的噪声？
    \end{itemize}
    
\end{frame}

\subsection{有噪信道} % Rate, Capacity

\begin{frame}
    \frametitle{信道}
    \begin{itemize}
        \item 符号集$\{a,b\}$，发送器以$100$符号每秒的速度发送消息
        \item 每个符号错误概率为$1\%$
        \item 有效的传输速度是多少符号每秒？
    \end{itemize}
    

\end{frame}

\begin{frame}[label=Appendix_fano_back]
    \frametitle{信道传输速率}
    \begin{itemize}
        \item 接收信号中丢失的部分
        \item 噪声(\textcolor{red}{疑义度})$\Longrightarrow H(X|Y)$
        \item 信道传输速率
        \begin{equation}
            R = H(X) - H(X|Y)
        \end{equation}
    \end{itemize}
    \hyperlink{Appendix_fano}{\beamergotobutton{Jump to Fano}}

\end{frame}

\begin{frame}
    \frametitle{信道容量}
    \begin{itemize}
        \item 可能实现的\textcolor{red}{最大传输速率}是信道的容量$C$
        \begin{equation}
            \begin{split}
                C & = \max\limits_{P(X)}\{H(X)-H(X|Y)\} \\
                & = \max\limits_{P(X)} I(X;Y)                
            \end{split}
        \end{equation}
    \end{itemize}

\end{frame}

\begin{frame}
    \frametitle{信道容量}
    \begin{itemize}
        \item 可能实现的\textcolor{red}{最大传输速率}是信道的容量$C$
        \begin{equation*}
            C = \max\limits_{P(X)}\{H(X)-H(X|Y)\}
        \end{equation*}
        \item 更一般的信道容量
        \begin{equation}
            C = \lim\limits_{N\rightarrow\infty}\frac{1}{N}\max\limits_{P(X^N)} I(X_1\cdots X_N;Y_1\cdots Y_N)
        \end{equation}
    \end{itemize}

\end{frame}

\subsection{信道编码定理}

\begin{frame}
    \frametitle{信道编码定理}
    \begin{theorem}[离散无记忆信道编码定理]
        离散信道容量为$C$，信号传输速率$R$，满足
        \begin{equation}
            R\leq C
        \end{equation}
        则存在编码使得输出信号疑义度任意小；否则，疑义度至少$R-C$
    \end{theorem}
    \begin{figure}[H]
        \centering
        \includegraphics[width=5cm]{chn_encode_thm}
        \caption{疑义度与给定传输速率的关系}
        \label{fig:chn_encode_thm}
    \end{figure}

\end{frame}

\begin{frame}
    \frametitle{信道编码定理}
    \begin{theorem}[离散无记忆信道编码定理]
        离散信道容量为$C$，信号传输速率$R$，满足
        \begin{equation}
            R\leq C
        \end{equation}
        则存在编码使得输出信号疑义度任意小；否则，疑义度至少$R-C$
    \end{theorem}
    \begin{figure}[H]
        \centering
        \includegraphics[width=5cm]{chn_encode_thm}
        \caption{疑义度与给定传输速率的关系}
        \label{fig:chn_encode_thm}
    \end{figure}

\end{frame}


\begin{frame}
    \frametitle{联合典型列}
    \begin{columns}[c]
        \column{5cm}
        \begin{itemize}
            \item $N$长的序列,传输速率为$R$,即传输$2^NR$条序列
            \item 输入中约$2^{NH(X)}$条典型列
            \item 输出中约$2^{NH)Y}$条典型列
        \end{itemize}

        \column{7cm}
        \begin{figure}[H]
            \vspace{-0.5cm}
            \centering
            \includegraphics[width=7cm]{joint_AEP}
            \caption{联合典型列示意}
            \label{fig:joint_AEP}
        \end{figure}
    \end{columns}
    
\end{frame}

\begin{frame}
    \frametitle{联合典型列}
    \begin{columns}[c]
        \column{5cm}
        \begin{itemize}
            \item 一条输入序列被传输的概率为$2^{N(R-H(X))}$
            \item 接收到未被传输序列的概率为$(1-2^{N(R-H(X))})^{2^{NH(X|Y)}}$(除去原始输入序列)
            \item 若$R=H(X)-H(X|Y)-\epsilon$
            \begin{equation}
                \begin{split}
                    &\lim\limits_{N                \rightarrow\infty}(1-2^{-N(H(X|Y)+\epsilon)})^{2^{NH(X|Y)}} \\
                    &= 1-2^{-N\epsilon} = 1
                \end{split}
            \end{equation}
        \end{itemize}

        \column{7cm}
        \begin{figure}[H]
            \vspace{-0.5cm}
            \centering
            \includegraphics[width=7cm]{joint_AEP}
            \caption{联合典型列示意}
            \label{fig:joint_AEP}
        \end{figure}
    \end{columns}
    
    

\end{frame}

\begin{frame}
    \frametitle{联合典型列}
    \begin{columns}[c]
        \column{5cm}
        \begin{itemize}
            \item 一条输入序列可能对应$2^{NH(Y|X)}$条输出序列
            \item 输出序列之间不发生重合
            \begin{equation}
                2^R2^{NH(Y|X)} < 2^{NH(Y)}
            \end{equation}
        \end{itemize}

        \column{7cm}
        \begin{figure}[H]
            \vspace{-0.5cm}
            \centering
            \includegraphics[width=7cm]{joint_AEP}
            \caption{联合典型列示意}
            \label{fig:joint_AEP}
        \end{figure}
    \end{columns}
    \hyperlink{reference}{\beamergotobutton{Jump to End}}
    
\end{frame}

\section{附录}

\subsection{熵的形式}

\begin{frame}[label=Appendix_entropy]
    \frametitle{熵}
    对等概率的熵$H(\frac{1}{n},\cdots,\frac{1}{n})\triangleq A(n)$
    
    为满足3(可加性)，对于m长序列有$A(s^m)=mA(s)$，同样的有$A(t^n) = nA(t)$

    选取$s,m,t,n$使得
    \begin{equation}
        \label{equ:entropy1}
        \begin{split}
            s^m\leq & t^n\leq s^{m+1} \\
            \frac{m}{n} \leq & \frac{\log t}{\log s} \leq \frac{m}{n} + \frac{1}{n}
        \end{split}
    \end{equation}

\end{frame}

\begin{frame}
    \frametitle{熵}
    
    为满足2(单调递增)，$A(s^m)\leq A(t^n)\leq A(s^{m+1})$

    即有
    \begin{equation}
        \label{equ:entropy2}
        \frac{m}{n} \leq \frac{A(t)}{A(s)} \leq \frac{m}{n} + \frac{1}{n}
    \end{equation}
    结合\autoref{equ:entropy1}和\autoref{equ:entropy2}，
    \begin{equation}
        \mid\frac{\log t}{\log s} - \frac{A(t)}{A(s)}\mid < \epsilon \Longleftrightarrow A(t) = K\log t
    \end{equation}

\end{frame}

\begin{frame}
    \frametitle{熵}
    推广到非等概情况，将等概率的$n$种情况分为$n = \sum n_i$，对应概率$p_i = \frac{n_i}{n}$

    利用3，
    \begin{equation}
        \begin{split}
            K\log n & = H(p_1,\cdots) + K\sum p_i\log n_i \\
            & \Longrightarrow \\
            H(p_1,\cdots) & = K\sum p_i\log \frac{1}{p_i}
        \end{split}
    \end{equation}
    \hyperlink{Appendix_entropy_back}{\beamergotobutton{Jump Back}}
\end{frame}

\subsection{典型列}
\begin{frame}[label=Appendix_AEP]
    \frametitle{典型列}
    考虑$N$长序列，符号$\{s_i\}$相互独立，理想的出现符号$s_i$的次数为$p_iN$

    设理想的序列分布为$Q(s^N) = \prod\limits_{i=1}^Np_i^{p_iN}$

    考察两个分布的差异
    \begin{equation}
        \begin{split}
            D(P\|Q) & = \sum P(s^N)\log \frac{P(s^N)}{Q(s^N)} \\
            & = \sum P(s^N)[\log P(s^N) - \log {Q(s^N)}] \\
            & = \text{E}[-\frac{\log P(s^N)}{N} - H(\mathcal{S})]
        \end{split}
    \end{equation}

    \begin{definition}[典型列(KL散度)]
        \begin{equation}
            A_\epsilon^{(N)} = \{s^N:D(P\|Q)\leq \epsilon\}
        \end{equation}
    \end{definition}
    
    \hyperlink{Appendix_AEP_back}{\beamergotobutton{Jump Back}}

\end{frame}

\begin{frame}[label=Appendix_fano]
    \frametitle{Fano不等式}
    \begin{theorem}[Fano不等式]
        $\mathcal{X}$为符号集，$Y$为对$X$的估计
        \begin{equation}
            H(X|Y) \leq H(P_e) + P_e\log(\mid\mathcal{X}\mid-1)
        \end{equation}
        其中，$P_e\triangleq P(X\neq Y)$
    \end{theorem}
    \begin{proof}
        \begin{equation*}
            \begin{split}
                H(X|Y) & = H(P_e) + P_eH(X|X\neq Y) \\
                & \leq H(P_e) + P_e\log(\mid\mathcal{X}\mid-1)
            \end{split}
        \end{equation*}
    \end{proof}
    \hyperlink{Appendix_fano_back}{\beamergotobutton{Jump Back}}


\end{frame}



\section{参考文献}
\begin{frame}[label=reference]
	\ftitle{Reference}
	\label{Reference}
	\footnotesize
    \bibliographystyle{ieeetr}	   % different styles, such as ieee
    \bibliography{MyCollection}  % make reference list
\end{frame}






\begin{frame}
    \frametitle{谢谢}
    \qquad \qquad \qquad \qquad \qquad \qquad \qquad 谢谢
    

\end{frame}


\end{document}
